package com.gali.leetcode.day10;

import java.util.*;
import java.util.logging.Level;

/**
 * @Auther: gali
 * @Date: 2022-07-23 18:32
 * @Description:下一个排列
 */
public class Solution {
    public void nextPermutation(int[] nums) {
        int length = nums.length;
        if (length<=0){
            return;
        }
        for (int i = length - 1; i >0 ; i--) {
            if (nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, length);//排序
                for (int j = i; j < length; j++) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        return;
                    }
                }
            }
        }
        Arrays.sort(nums);
        return;
    }

    /**
     * 最长有效括号--栈
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        if (s==null||s.length()==0){
            return 0;
        }
        int max=0;//最终返回的长度
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='('){
                stack.push(i);
            }else {
                stack.pop();
                if (stack.isEmpty()){
                    stack.push(i);
                }else {
                    max=Math.max(max,i-stack.peek());
                }
            }
        }
        return max;
    }
}
